package mashibing.class21;

/**
 * 给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角
 * 沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和
 * 返回最小距离累加和
 */
public class Class21_1_MinPathSum {

    // dp
    public static int minPathSum1(int[][] m) {
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return 0;
        }
        int row = m.length;
        int col = m[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = m[0][0];
        for (int j = 1; j < col; j++) {
            dp[0][j] = dp[0][j - 1] + m[0][j];
        }
        for (int i = 1; i < row; i++) {
            dp[i][0] = dp[i - 1][0] + m[i][0];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
            }
        }
        return dp[row - 1][col - 1];
    }

    // 空间压缩
    public static int minPathSum2(int[][] m) {
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return 0;
        }
        int row = m.length;
        int col = m[0].length;
        int[] dp = new int[col];
        dp[0] = m[0][0];
        for (int j = 1; j < col; j++) {
            dp[j] = dp[j - 1] + m[0][j];
        }
        for (int i = 1; i < row; i++) {
            dp[0] = dp[0] + m[i][0];
            for (int j = 1; j < col; j++) {
                dp[j] = Math.min(dp[j - 1], dp[j]) + m[i][j];
            }
        }
        return dp[col - 1];
    }


    public static void main(String[] args) {
        // 760
        int[][] m = {{90, 23, 64, 75, 63, 75, 89, 85, 93, 37}, {39, 35, 97, 22, 22, 28, 32, 92, 33, 95}, {15, 22, 56, 83, 73, 34, 4, 79, 95, 65}, {35, 30, 59, 88, 6, 9, 88, 39, 18, 36}, {98, 33, 90, 89, 94, 36, 34, 76, 93, 80}, {66, 81, 18, 86, 58, 52, 99, 0, 65, 29}, {8, 26, 85, 77, 28, 92, 90, 32, 6, 65}, {71, 31, 38, 86, 31, 62, 73, 90, 65, 12}, {77, 30, 89, 86, 52, 40, 51, 27, 73, 99}, {36, 27, 80, 24, 82, 16, 81, 17, 6, 84}};
        System.out.println(minPathSum1(m));
        System.out.println(minPathSum2(m));
    }
}
